CS-04 : DATA STRUCTURE THROUGH 'C' & PASCAL  DEC 1999

NOTE: Question 1 is compulsory. Attempt any three from the rest.  Algorithms should be written near to C or Pascal language statements.
 

1.	(a).	A dequeue (double ended queue) is a list from which elements can be inserted or deleted at either end.  Develop array and pointer implementations for a dequeue.
	(b)	The following keys are to be inserted in the order shown into an AVL tree: 50, 45, 80, 95, 43, 105, 2 Show how the tree appears after each insertion.
	(c)	The degree of a node is the number of children it has.  Show that in any binary tree, the number of leaves us one more than the number of nodes of degree two.
2.	(a)	Compare and contrast circular linked lists and doubly linked lists.
	(b)	The order of nodes of a Binary tree in preorder and inorder traversal are as under:
		Preorder:  A  B  C D  F  H  J  M  K  E  G  I L N Inorder  :   A  D  J M  H K  F  C  I   N  L  G E B
3.	(a)	If 'm' and 'n' are two different nodes in the same tree, show that exactly one of the following statements is true: (i)   'm' is to the left of 'n' (ii)  'm' is to the right of 'n' (iii) 'm' is a proper ancestor of 'n' (iv) 'm' is a proper descendant of 'n'
	(b)	Write a program to compute the height of a tree which uses Leftmost-Child, Right-Sibling representation.
4.	(a)	Consider the graph of following figure :
		Find a breadth-first spanning tree at 'a' and at 'd'.
	(b)	Write an algorithm to find a longest simple path from a given vertex of a digraph.  What is the time complexity of program ?
5.	(a)	suppose you are to sort a list L consisting of a sorted list followed by a few "random" elements.  Which of the sorting methods would be suitable for such a task and why ?
	(b)	suppose we have a sorted array of strings S1,S2, S3........Sn. Write a program  to determine whether a given string 'x' is a member of this sequence.  What is the time complexity of your program as a function of 'n' and the length of 'x' ?
6.		Discuss the differences between the following file organization techniques: * Sequential file organization * Index Sequential file organization * Direct  file organization Compare their storage and access efficiencies.  To What type of applications are each of the techniques suited ? Give one application for each file organization and justify your association of that application with that file organization.